package _动态规划系列._编辑距离;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: 吕庆龙
 * @Date: 2020/3/30 17:33
 * <p>
 * 功能描述:
 */
public class Summary_0072 {

    public static void main(String[] args) {
        Summary_0072 test = new Summary_0072();
        test.minDistance1("a", "ab");

    }

    /**
     * 自顶向下的动态规划
     */
    Map<String, Integer> memo = new HashMap<>();

    public int minDistance1(String word1, String word2) {

        return dpHelper(word1, word2, word1.length() - 1, word2.length() - 1);
    }

    public int dpHelper(String word1, String word2, int i, int j) {

        String key = i + "-" + j;
        if (memo.containsKey(key))
            return memo.get(key);

        if (i == -1)
            return j + 1;
        if (j == -1)
            return i + 1;
        int res;
        if (word1.charAt(i) == word2.charAt(j)) {
            res = dpHelper(word1, word2, i - 1, j - 1);
        } else {

            int a = dpHelper(word1, word2, i - 1, j - 1) + 1;
            int b = dpHelper(word1, word2, i, j - 1) + 1;
            int c = dpHelper(word1, word2, i - 1, j) + 1;

            res = Math.min(a,Math.min(b,c));
        }

        memo.put(key, res);
        return res;
    }


    /**
     * 自底向上的动态规划
     * 定义dp[i][j]: 对于word1[0...i-1]和word2[0..j-10]的最短编辑距离
     */
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1];

        //base case
        for (int j = 0; j < n + 1; j++) {
            dp[0][j] = j;
        }

        for (int i = 0; i < m + 1; i++) {
            dp[i][0] = i;
        }

        //
        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {

                //做选择。通过不同的选择，来进行不同的状态转移
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(
                            dp[i - 1][j - 1] + 1,  //替换
                            Math.min(dp[i][j - 1] + 1, //插入
                                    dp[i - 1][j] + 1));  //删除
                }
            }
        }

        return dp[m][n];
    }


}
